package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @ClassName Medium_56_MergeOverLaping
 * @Description 我的题解：https://leetcode.cn/problems/merge-intervals/solution/zhong-deng-56-he-bing-qu-jian-qu-qiao-by-si7m/
 * @Author wanghaiwei
 * @Date 2023/3/2 10:03
 */
public class Medium_56_MergeOverLaping {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{};
        }
        if (intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(r -> r[0]));
        Map<Integer, Integer> overlappingStartAndEnd = new HashMap<>();
        overlappingStartAndEnd.put(intervals[0][0], intervals[0][1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[i - 1][1]) {
                //有重叠，合并到i位置
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
            }
            overlappingStartAndEnd.put(intervals[i][0], intervals[i][1]);
        }
        int[][] result = new int[overlappingStartAndEnd.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : overlappingStartAndEnd.entrySet()) {
            int[] newInterval = new int[2];
            newInterval[0] = entry.getKey();
            newInterval[1] = entry.getValue();
            result[i] = newInterval;
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        Medium_56_MergeOverLaping solution = new Medium_56_MergeOverLaping();
        String result = Arrays.stream(solution.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})).map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(","));
        Assert.isTrue("[1,6],[8,10],[15,18]".equals(result), "intervals = [[1,3],[2,6],[8,10],[15,18]]计算错误，预期:[1,6],[8,10],[15,18]，实际：" + result);
        result = Arrays.stream(solution.merge(new int[][]{{1, 4}, {4, 5}})).map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(","));
        Assert.isTrue("[1,5]".equals(result), "intervals = [[1,4],[4,5]]计算错误，预期:[1,5]，实际：" + result);

        result = Arrays.stream(solution.merge(new int[][]{{1, 4}, {0, 4}})).map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(","));
        Assert.isTrue("[0,4]".equals(result), "intervals = [[1,4],[0,4]]计算错误，预期:[0,4]，实际：" + result);

        result = Arrays.stream(solution.merge(new int[][]{{1, 4}, {2, 3}})).map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(","));
        Assert.isTrue("[1,4]".equals(result), "intervals = [[1,4],[2,3]]计算错误，预期:[1,4]，实际：" + result);
    }
}
